High speed networked packet switching communications systems commonly use table look-up operations to match a field or a set of fields against a table of entries. For example, Internet protocol (IP) routing operations commonly apply longest prefix match (LPM) comparison techniques to perform forwarding table look-ups. Access control list (ACL) filtering operations commonly apply masked match comparison techniques involving one or more fields to perform ACL table look-ups. Network address translation (NAT) operations also apply masked match comparison techniques involving one or more fields to perform NAT table look-ups. So-called “exact match” table look-ups, in which a multiple-field input key is matched against a table of keys to determine whether the table contains a key which exactly matches the input key, are commonly used in performing asynchronous transfer mode virtual packet identifier and virtual circuit identifier (ATM VPI/VCI) table look-ups, multi-protocol label switching (MPLS) label look-ups, transmission control protocol/Internet protocol (TCP/IP) flow identification look-ups, etc.
As one example, TCP/IP flow identification involves a flow table look-up in which a 5-tuple key, consisting of a packet's source IP address (SIP), destination IP address (DIP), source port (SP), destination port (DP) and protocol fields is used to identify packet “flow.” For example, the 5-tuple {192.1.4.5, 200.10.2.3, 21, 1030, tcp} corresponds to SIP 192.1.4.5, DIP 200.10.2.3, SP 21, DP 1030 and protocol tcp. An input 5-tuple key is compared with 5-tuple keys stored in a flow table to determine whether one of the keys stored in the table exactly matches the input key. Each key in the table is stored with other information which can be retrieved and utilized to obtain packet flow information, if a stored key corresponding to the input key is located.
Flow tables can be very large. For example, a flow table suitable for use at an OC-48 line rate (2.4 Gbps) typically contains millions of entries. To accommodate such line rates the exact match table look-up operation must be extremely fast and it should be deterministic in the sense that the look-up operation should have a very high probability of successfully locating an input key in a very large table within a short finite interval on the order of a few nanoseconds.
A variety of hardware and software approaches have been used to perform exact match look-up operations on large tables, with varying degrees of efficacy. One hardware solution utilizes content addressable memory (CAM) or ternary content addressable memory (TCAM). CAM/TCAM devices facilitate extremely fast, parallel (i.e., simultaneous) look-up operations on all keys stored in a table. However, table size is limited, due to the relatively high power consumption of CAM/TCAM devices and due to the cost and complexity of apparatus incorporating the large number of CAM/TCAM devices required to contain even modestly large table. Consequently, currently available CAM/TCAM devices are not well suited to exact match look-up operations on very large tables. Hardware based trie/tree walking techniques are also impractical, since their performance is reduced by the requisite large number of memory accesses and by relatively long table update times. Single and multilevel hashing techniques are also commonly used to perform exact match look-up operations on large tables, but such techniques are constrained by the fact that the look-up operation is non-deterministic (due to the fact that hashing techniques normally use a linear walk to differentiate between collided entries), by inefficient use of memory and by relatively low performance.